
// Ahmad Salama & Amine Allaouchiche
//

#include "graphl.h"

//Constructor:-----------------------------------------------------------------
GraphL::GraphL()
{
	this->size = 0;
	this->graphNodes = NULL;
}

//Destructor:------------------------------------------------------------------
GraphL::~GraphL()
{
	delete [] this->graphNodes;
}

//buildGraph:------------------------------------------------------------------
void GraphL::buildGraph(ifstream& reader)
{
	while ( !reader.eof())
	{
		int size ;
		reader >> size ;

		//Initilize Size:
		this->size = size + 1;
		this->graphNodes = new GraphNode[this->size];		

		string s;
		getline (reader,s);		
		// this loop reads the lines containing the nodes data		
		for(int i = 1; i < this->size; i++)
		{
			getline (reader,s);
			graphNodes[i].index = i;
			graphNodes[i].visited = false;
			graphNodes[i].edgeHead = NULL;	

			if(graphNodes[i].data != NULL)
			{
				graphNodes[i].data = NULL;
				delete graphNodes[i].data;
			}
			graphNodes[i].data = new NodeData(s);	//Memory leak		
		}			

		//this loop reads the graph info: source target
		int source, target;		

		for(reader >> source, reader >> target; (source != 0) && (target != 0); reader >> source, reader >> target)
		{
			//Add target to source's list:
			this->insertEdge(source, target);
		}
		break;
	}
}

//displayGraph:----------------------------------------------------------------
void GraphL::displayGraph()
{
	cout << "\tGraph: " << endl;

	for(int i = 1; i < this->size; i++)
	{
		cout << "\tNode: " << this->graphNodes[i].index << "\t\t" << *(this->graphNodes[i].data) << endl;

		for(EdgeNode* current = this->graphNodes[i].edgeHead;  current != NULL; current = current->nextEdge)
		{
			cout << "\t   Edge  " <<  this->graphNodes[i].index << "  " << current->adjGraphNode << endl;
		}
		cout << endl;
	}
}

//insertEdge:------------------------------------------------------------------
void GraphL::insertEdge(int source, int target)
{
	EdgeNode* ptr= new EdgeNode(); // Memory leak;
	if (ptr == NULL)
	{
		return; 
	}// out of memory, bail

	ptr->adjGraphNode = target;

	// if the list is empty or if the node should be inserted before 
	// the first node of the list
	if (this->graphNodes[source].edgeHead == NULL || ptr->adjGraphNode < this->graphNodes[source].edgeHead->adjGraphNode)
	{
		ptr->nextEdge = this->graphNodes[source].edgeHead;		
		this->graphNodes[source].edgeHead = ptr;
	}

	// then check the rest of the list until we find where it belongs 
	else {
		EdgeNode* current = this->graphNodes[source].edgeHead->nextEdge;          // to walk list
		EdgeNode* previous = this->graphNodes[source].edgeHead;               // to walk list, lags behind

		// walk until end of the list or found position to insert
		while (current != NULL && current->adjGraphNode < ptr->adjGraphNode) {
			previous = current;                  // walk to next node
			current = current->nextEdge;
		}

		// insert new node, link it in
		ptr->nextEdge = current; 
		previous->nextEdge = ptr;		
	}	
	return;
}

//depthFirstSearch:------------------------------------------------------------
void GraphL::depthFirstSearch()
{
	cout << endl;	
	cout << "\tDepth-first ordering: ";
	for(int i = 1; i < this->size; i++)
	{
		if(! this->graphNodes[i].visited)
		{
			this->breadthFirst(&this->graphNodes[i]);
		}
	}
	cout << endl;
	cout << endl;
}

//Private Members:

//getCount():------------------------------------------------------------------
int GraphL::getCount()
{
	return this->size - 1;
}

//breadthFirst:----------------------------------------------------------------
void GraphL::breadthFirst(GraphNode* curr)
{
	if(curr == NULL)
	{
		return;
	}
	curr->visited = true;
	int index = curr->index;
	cout << index << "  ";
	//Loop through its adjacents:
	for(EdgeNode* current = curr->edgeHead;  current != NULL; current = current->nextEdge)
	{
		if(!this->graphNodes[current->adjGraphNode].visited)
		{
			breadthFirst(&this->graphNodes[current->adjGraphNode]);
		}
	}
}
